package com.hr.剑指offer.work1;

/**
 * @author 周恒哲
 * @date 2020/06/17
 * 1、初始化： 伪头节点 dum ，节点 cur 指向 dum 。
 * 2、循环合并： 当 l1或 l2为空时跳出；
 *      1、当 l1.val<l2.val 时： cur 的后继节点指定为 l1，并 l1向前走一步；
 *      2、当 l1.val≥l2.val 时： cur 的后继节点指定为 l2，并 l2向前走一步 ；
 *      3、节点 cur 向前走一步，即 cur = cur.nextcur=cur.next 。
 * 3、合并剩余尾部： 跳出时有两种情况，即 l1为空 或 l\2为空。
 *      1、若 l1 != null ： 将 l1添加至节点 cur 之后；
 *      2、否则： 将 l2添加至节点 cur 之后。
 * 4、返回值： 合并链表在伪头节点 dumdum 之后，因此返回 dum.next即可。
 **/
public class 面试题25_合并两个排序的链表 {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dum=new ListNode(0);
        ListNode cur=dum;
        while (l1!=null&&l2!=null){
            if (l1.val<l2.val){
                cur.next=l1;
                l1= l1.next;
            }else{
                cur.next=l2;
                l2= l2.next;
            }
            cur=cur.next;
        }
        cur.next=l1!=null?l1:l2;
        return dum.next;
    }
}
